package Lee_code;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.stream.Collectors;

/**
 * @author blh
 * @date 2024年08月26日 9:38
 */
public class Lee_752_826 {

    public int openLock(String[] deadends, String target) {

        // 锁的初始数字为 '0000'
        HashSet<String> deadEnds = (HashSet<String>) Arrays.stream(deadends).collect(Collectors.toSet());
        HashSet<String> seen = new HashSet<>();
        Deque<String> deque = new ArrayDeque<>();
        if ("0000".equals(target)){
            return 0;
        }
        deque.add("0000");
        int step = 0;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                String tempStr = deque.poll();
                char[] tempChars = tempStr.toCharArray();
                if (deadEnds.contains(tempStr)) {
                    continue;
                }
                seen.add(tempStr);
                step++;
                for (int j = 0; j < 4; j++) {
                    char tempChar = tempChars[j];
                    char[] chars = nextChar(tempChar);

                    for (int i1 = 0; i1 < chars.length; i1++) {
                        char[] tisigui = tempChars.clone();
                        tisigui[j] = chars[i1];
                        if (seen.contains(new String(tisigui))) {
                            continue;
                        }
                        if (new String(tisigui).equals(target)) {
                            return step;
                        }
                        seen.add(new String(tisigui));
                        deque.offer(new String(tisigui));
                    }
                }
            }
        }
        return -1;
    }

    public char[] nextChar(char i) {
        char[] res = new char[2];
        res[0] = (char) (i - 1);
        res[1] = (char) (i + 1);
        if (i == '0') {
            res[0] = (char) (i + 9);
        } else if (i == '9') {
            res[1] = (char) (i - 9);
        }
        return res;
    }
}
